home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 15645 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.7 KB
  1. Path: solon.com!not-for-mail
  2. From: bcalbridge@dcccd.edu (Bob Calbridge)
  3. Newsgroups: comp.lang.c,comp.lang.c.moderated
  4. Subject: Re: 8 Queens prog help
  5. Date: 20 Apr 1996 13:34:50 -0500
  6. Organization: D C C C D
  7. Sender: clc@solutions.solon.com
  8. Approved: clc@solutions.solon.com
  9. Message-ID: <4lbaoa$lku@solutions.solon.com>
  10. References: <4l87ud$73u@solutions.solon.com>
  11. NNTP-Posting-Host: solutions.solon.com
  12. X-Newsreader: Forte Free Agent 1.0.82
  13.  
  14. Mike Mitchell <72724.2067@CompuServe.COM> wrote:
  15.  
  16. >Hi All!
  17.  
  18. >Need some C help this week.  I'm currently working on a program 
  19. >called "Eight Queens".  Basically, I have to place 8 queen chess 
  20. >pieces on an 8x8 chess board without them checking one another.  
  21. >The instructer wants us to use a "backtracking algorithm" (i.e. a 
  22. >tree structure) to accomplish this.  My thoughts thus far are to 
  23. >place my first queen randomly and mark that space with a 'Q' 
  24. >character and then mark off all the squares in its legal paths 
  25. >(all adjacent squares vertical, horizontal, and diagonal to the 
  26. >ends of the board) with an 'X' character.  Board is initialized 
  27. >to Nulls.
  28.  
  29. >When the next queen piece is placed I will check to see if 
  30. >another queen is in one of its paths.  If there isn't I will 
  31. >place the piece and mark off its paths otherwise I will return 
  32. >the square to NULL and move to the next NULL square.
  33.  
  34. >Am I approaching this the right way or should I be handling this 
  35. >another way?  Can someone explain how a tree structure 
  36. >accomplishes this?
  37.  
  38. >We did a similar problem in class using the knight piece and its 
  39. >legal moves.  Well, needless to say the number of legal moves a 
  40. >queen can make, make this problem a little more difficult. 
  41.  
  42. Hmmm.  Not sure what you mean by a tree structure in this instance.
  43. The only time I've tackled this problem I used recursion and brute
  44. force.  The method you speak of is probably a bit faster than mine but
  45. mine did produce all non-unique solutions where yours just seems to
  46. produce one random solution.  
  47.  
  48. It seems to me that if each subsequent piece placement finds a null
  49. square there should no reason to check your paths to see if there's
  50. conflict.  Otherwise it wouldn't be a null square to begin with.
  51.  
  52. I'm not sure why you say that the queen's problem is more difficult
  53. than the knight's problem.  I'm assuming that it was a matter of
  54. placing eight knights on the board?  It would seem to me that the
  55. prospect of mapping eight elimination squares in a non-linear
  56. arrangement is more complex than the straight paths a queen moves on.
  57. Just wait 'til you try to move a knight from a single starting point
  58. to all 64 squares without revisiting any squares.  :-(
  59.  
  60. Bob
  61. Bob Calbridge = bcalbridge@dcccd.edu
  62. Senior Network Systems Programmer
  63. Postmaster, Cook, Bottle Washer
  64.